package _dp_base;

/**
 * 1312. 让字符串成为回文串的最少插入次数
 */
public class No1312 {
    char[] chars1, chars2;

    /*
      一、线性DP
     */

    /**
     * 1. 递归
     */
    public int minInsertions11(String s) {
        int n = s.length();
        this.chars1 = s.toCharArray();
        this.chars2 = new char[n];
        for (int i = 0; i < n; i++) {
            chars2[i] = s.charAt(n - 1 - i);
        }
        return n - dfs1(n - 1, n - 1);
    }

    private int dfs1(int i, int j) {
        if (i < 0 || j < 0) return 0;
        else if (chars1[i] == chars2[j]) return dfs1(i - 1, j - 1) + 1;
        else return Math.max(dfs1(i - 1, j), dfs1(i, j - 1));
    }

    /**
     * 2. 迭代
     */
    public int minInsertions12(String s) {
        int n = s.length();
        int[][] f = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s.charAt(i) == s.charAt(n - 1 - j)) f[i + 1][j + 1] = f[i][j] + 1;
                else f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
            }
        }
        return n - f[n][n];
    }

    /**
     * 4. 空间优化
     */
    public int minInsertions14(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int pre = f[0];
            for (int j = 0; j < n; j++) {
                int temp = f[j + 1];
                if (s.charAt(i) == s.charAt(n - 1 - j)) f[j + 1] = pre + 1;
                else f[j + 1] = Math.max(f[j + 1], f[j]);
                pre = temp;
            }
        }
        return n - f[n];
    }

    /*
      二、区间DP
     */

    private String s;

    /**
     * 1. 递归
     */
    public int minInsertions21(String s) {
        this.s = s;
        int n = s.length();
        return dfs2(0, n - 1);
    }

    private int dfs2(int i, int j) {
        if (i >= j) return 0;
        else if (s.charAt(i) == s.charAt(j)) return dfs2(i + 1, j - 1);
        else return Math.min(dfs2(i + 1, j) + 1, dfs2(i, j - 1) + 1);
    }

    /**
     * 2. 迭代
     */
    public int minInsertions22(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) f[i][j] = f[i + 1][j - 1];
                else f[i][j] = Math.min(f[i + 1][j] + 1, f[i][j - 1] + 1);
            }
        }
        return f[0][n - 1];
    }

    /**
     * 4. 空间优化
     */
    public int minInsertions24(String s) {
        int n = s.length();
        int[] f = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int pre = 0;
            for (int j = i + 1; j < n; j++) {
                int temp = f[j];
                if (s.charAt(i) == s.charAt(j)) f[j] = pre;
                else f[j] = Math.min(f[j] + 1, f[j - 1] + 1);
                pre = temp;
            }
        }
        return f[n - 1];
    }

}
